package sort;

import java.util.Stack;

public class QuickSort {
    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 1, 0, 4, 5};
//        quickSort(array, 0, array.length - 1);
        quickSortRecursion(array, 0, array.length - 1);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }

    public static void quickSort(int[] array, int left, int right){
        Stack<Integer> st = new Stack<>();
        st.add(left);
        st.add(right);

        while (!st.isEmpty()){
            int r = st.pop();
            int l = st.pop();

            int index = partSort(array, l, r);

            //左半部分[l, index-1]
            if (index - 1 > l) {
                st.add(l);
                st.add(index-1);
            }

            //右半部分[index+1, r]
            if(index + 1 < r) {
                st.add(index+1);
                st.add(r);
            }

        }
    }

    public static void quickSortRecursion(int[] array, int left, int right){
        if(left >= right) return;
        int index = partSort(array, left, right);
        quickSortRecursion(array, left, index-1);
        quickSortRecursion(array, index+1, right);
    }


    public static int partSort(int[] array, int l, int r) {
        int pivot = array[r];
        int left = l, right = r;
        while (left < right) {
            while (left < right && array[left] <= pivot){
                left++;
            }
            while (left < right && array[right] >= pivot){
                right --;
            }
            swap(array, left, right);
        }
        swap(array, left, r);
        return left;
    }

    public static void swap(int[]array, int i, int j){
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
}
